Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost

In the last decade, there has been much progress in understanding scheduling problems in which selfish jobs aim to minimize their individual completion time. Most of this work has focused on makespan minimization as social objective. In contrast, we consider as social cost the total weighted completion time, that is, the sum of the agent costs, a standard definition of welfare in economics. In our setting, jobs are processed on restricted uniform parallel machines, where each machine has a speed and is only capable of processing a subset of jobs; a job's cost is its weighted completion time; and each machine sequences its jobs in weighted shortest processing time (WSPT) order. Whereas for the makespan social cost the price of anarchy is not bounded by a constant in most environments, we show that for our minsum social objective the price of anarchy is bounded above by a small constant, independent of the instance. Specifically, we show that the price of anarchy is exactly 2 for the class of unit jobs, unit speed instances where the finite processing time values define the edge set of a forest with the machines as nodes. For the general case of mixed job strategies and restricted uniform machines, we prove that the price of anarchy equals 4. From a classical machine scheduling perspective, our results establish the same constant performance guarantees for WSPT list scheduling. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

基于任务需求的系统保障性目标确定

从系统任务需求出发,提出了使用性能特性和保障特性的概念,并分析了二者之间的相互关系,同时给出了保障性目标的组成、内容和要求。介绍了确定保障性目标所用的方法,包括使用研究,剖面制定,比较分析,目标评估与改进以及目标实现。最后,给出了保障性目标要求确定的案例。     

维修任务调度的多目标决策模型

通过对维修调度问题进行分析,考虑到战斗力相关的多种目标因素,针对目前研究的目标单一,又未考虑武器的先进程度、配置等缺陷,就修复后的加权作战时间和装备尽可能少的延误数量双重目标加以研究,并给出了调度算法。从而弥补了这些缺陷,使调度更加合理。最后,算例表明模型的求解方法简单,计算时间较短,可有效地实现维修任务调度。     

有人机—无人机群协同空战目标分配算法

针对有人机—无人机群协同空战目标分配问题,运用离散粒子群算法,分为1架UCAV分配1个目标,1架UCAV分配2个目标时不考虑攻击先后影响和考虑攻击先后影响3种情况进行了仿真研究,提出了一种新的粒子构造方法。综合考虑空战能力指数和优势函数,构造了收益风险矩阵和多目标分配的代价函数。仿真结果具有良好收敛性,对有人机—无人机群协同空战目标分配具有参考价值。     

浅析武警部队职务防卫权

武警部队作为国家武装力量的重要组成部分,职务防卫权有其特殊的性质。从阐述职务防卫与一般正当防卫的区别着手,针对武警行使职务防卫权的客观需求进行分析,并结合当前武警部队行使职务防卫权的现状,对下一步的立法完善提出建议。     

投掷式通信干扰机的战斗任务级效能评估模型

针对投掷式通信干扰机战斗任务级效能评估不足的问题,在分析其典型作战任务的基础上,提出了战斗任务级效能指标——压制概率,依据对空域、频域、时域的覆盖要求,建立了压制概率的评估数学模型,进行了典型作战任务下压制概率的实例分析,分析结果表明:该指标及模型能比较准确地反应通信发射机与任务区域的相对位置、干扰机排布样式、干扰机数量等因素对投掷式通信干扰机战斗任务级效能的影响.     

Multi‐period maintenance scheduling of tree networks with minimum flow disruption

We introduce a multi‐period tree network maintenance scheduling model and investigate the effect of maintenance capacity restrictions on traffic/information flow interruptions. Network maintenance refers to activities that are performed to keep a network operational. For linear networks with uniform flow between every pair of nodes, we devise a polynomial‐time combinatorial algorithm that minimizes flow disruption. The spiral structure of the optimal maintenance schedule sheds insights into general network maintenance scheduling. The maintenance problem on linear networks with a general flow structure is strongly NP‐hard. We formulate this problem as a linear integer program, derive strong valid inequalities, and conduct a polyhedral study of the formulation. Polyhedral analysis shows that the relaxation of our linear network formulation is tight when capacities and flows are uniform. The linear network formulation is then extended to an integer program for solving the tree network maintenance scheduling problem. Preliminary computations indicate that the strengthened formulations can solve reasonably sized problems on tree networks and that the intuitions gained from the uniform flow case continue to hold in general settings. Finally, we extend the approach to directed networks and to maintenance of network nodes. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

遥感数据处理任务调度的Petri网模型及求解算法

为了对多源遥感数据的处理任务进行有效的调度和管理,提高处理资源的利用率,根据遥感数据处理任务调度问题的特点,采用Petri网对该问题进行形式化描述,建立了遥感数据处理任务调度的数学模型,根据该问题的多目标特性,采用蚁群算法进行求解.给出仿真实例,将蚁群算法的求解结果与启发式算法和模拟退火算法的求解结果进行比较,验证算法...     

Cyclic scheduling in robotic flowshops with bounded work‐in‐process levels

This study addresses cyclic scheduling in robotic flowshops with bounded work‐in‐process (WIP) levels. The objective is to minimize the cycle time or, equivalently, to maximize the throughput, under the condition that the WIP level is bounded from above by a given integer number. We present several strongly polynomial algorithms for the 2‐cyclic robotic flowshop scheduling problems for various WIP levels. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 1–16, 2011     

科学工作流技术研究综述

科学工作流管理系统(Scientific Workflow Management Systems,SWfMS)为科学家提供一个管理大规模复杂科学计算的有效平台,通过管理复杂应用程序对海量科学数据进行管理、分析、仿真和可视化以帮助科学家进行科学发现.本文首先对科学工作流(Scientific Workflow,SWF)...